Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Remove Duplicate Letters

Problem Statement

Given a string s, remove all duplicate letters from the input string while maintaining the original order of the letters.

Additionally, the returned string should be the smallest in lexicographical order among all possible results.

A string is in the smallest lexicographical order if it appears first in a dictionary. For example, "abc" is smaller than "acb" because "abc" comes first alphabetically.

Examples:

    • Input: "babac"
    • Expected Output: "abc"
    • Justification:
      • After removing 1 b and 1 a from the input string, we can get bac, and abc strings. The final answer is 'abc', which is the smallest lexicographical string without duplicate letters.
    • Input: "zabccde"
    • Expected Output: "zabcde"
    • Justification: Removing one of the 'c's forms 'zabcde', the smallest string in lexicographical order without duplicates.
    • Input: "mnopmn"
    • Expected Output: "mnop"
    • Justification: Removing the second 'm' and 'n' gives 'mnop', which is the smallest possible string without duplicate characters.

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Solution

To solve the given problem, begin by iterating through the string, and calculate the frequency count for each character. We will use the stack to maintain the order of characters and the set to track the uniqueness of characters.

Next, start traversing the string, and for every character encountered, check if it's already in the 'present' set. If it's not, compare it with the top element of the 'result' stack. If the stack is not empty, and the current character is lexicographically smaller than the stack's top, and the top character of the stack appears again in the string (indicated by a non-zero frequency count), repeatedly pop the stack and remove those elements from the 'present' set. Then, add the current character to the stack and the 'present' set.

This process, facilitated by the stack and set, ensures that the stack is built with unique characters in the smallest lexicographical order. After processing the entire string, pop elements from the stack to construct the final string, thereby obtaining the smallest lexicographical sequence without duplicate characters.

  1. Frequency Count (count):

    • Initialize a count dictionary (or hash map in some languages) to store the frequency of each character in the string s.
  2. Character Presence Tracking (present):

    • Use a set present to keep track of the characters that have been added to the resultant string. This set prevents duplicate characters in the result.
  3. Building the Result (result):

    • Create a stack result to construct the final string.
    • For each character c in the string s:
      • If c is not in present, proceed to compare it with the top character of result.
      • While result is not empty, and c is lexicographically smaller than the top character of result, and the frequency of the top character of result is more than 0 (indicating it appears again in the string), pop the top character from result and remove it from present.
      • Push c onto result and add it to present.
      • Decrement the frequency of c in count.
  4. Result Construction:

    • The stack result now contains the characters of the final string in reverse order. Pop elements from result to construct the output string in the correct order, from left to right.

This approach works because it ensures that the smallest character is placed first, respecting the original order and removing duplicates. The frequency count ensures that characters are not wrongly discarded.

Algorithm Walkthrough:

Input: "zabccde"

  1. Initialization:

    • Calculate the frequency of each character: {'z': 1, 'a': 1, 'b': 1, 'c': 2, 'd': 1, 'e': 1}.
    • Initialize an empty stack result and a set present to keep track of characters already in result.
  2. Iteration Over Characters:

    • 'z': Not in present. Add 'z' to result, add to present. Decrease frequency of 'z'.
    • 'a': Not in present. As 'a' is smaller than 'z', but 'z' won't appear again (frequency is now 0), we keep 'z'. Add 'a' to result, add to present. Decrease frequency of 'a'.
    • 'b': Not in present. Add 'b' to result, add to present. Decrease frequency of 'b'.
    • First 'c': Not in present. Add 'c' to result, add to present. Decrease frequency of 'c'.
    • Second 'c': Already in present. Skip it.
    • 'd': Not in present. Add 'd' to result, add to present. Decrease frequency of 'd'.
    • 'e': Not in present. Add 'e' to result, add to present. Decrease frequency of 'e'.
  3. Result Construction:

    • The result stack now contains ['z', 'a', 'b', 'c', 'd', 'e'].
    • Convert the stack to a string to get the final result: "zabcdef".

Expected Output: "zabcdef"

Image

Code

Here is the code for this algorithm:

Java

. . . .

Complexity Analysis:

  • Time Complexity: O(N) where N is the length of the string. Each character is visited once.
  • Space Complexity: O(1) as the extra space used does not depend on the input size. The character count and the stack size are bounded by the character set size (constant).
Remove Duplicate Letters (medium)
Longest Substring Without Repeating Characters (medium)
Mark as Completed

On this page

Problem Statement

Solution

Code

Complexity Analysis: